package interviewpreparationkit.sorting

/**
 * [Fraudulent Activity Notifications](https://www.hackerrank.com/challenges/fraudulent-activity-notifications)
 */
// Complete the activityNotifications function below.
fun activityNotifications(expenditure: Array<Int>, d: Int): Int {
    val m = d / 2
    val bucket = Array(200) { 0 }

    fun selectMedian2(): Int {
        if (d % 2 == 1) {
            var k = m
            for (i in 0..199) {
                k -= bucket[i]
                if (k < 0) {
                    return i * 2
                }
            }
        } else {
            var k = m - 1
            var j = 0
            for (i in 0..199) {
                k -= bucket[i]
                if (k < -1) {
                    return 2 * i
                } else if (k < 0) {
                    j = i
                    break
                }
            }
            for (i in (j + 1)..199) {
                if (bucket[i] > 0) {
                    return i + j
                }
            }
        }
        return -1
    }

    val queue = Array(d) {
        val item = expenditure[it]
        bucket[item]++
        item
    }
    var c = 0
    var ans = 0
    var t: Int
    var median2: Int
    var polled: Int
    for (i in d until expenditure.size) {
        polled = queue[c]
        t = expenditure[i]
        median2 = selectMedian2()

        if (t >= median2) {
            ans++
        }
        if (polled != t) {
            bucket[polled]--
            bucket[t]++
        }
        queue[c] = t
        c = (c + 1) % d
    }
    return ans
}